/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=GACS25

␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βdRECURSIVE PROGRAMMING AND PROVING  ␈↓ 
0FALL 1979

␈↓ ↓H␈↓␈↓ ¬DPROBLEM SET  0
␈↓ ↓H␈↓␈↓ ¬|Due  Oct. 5

␈↓ ↓H␈↓        Below␈αare␈α
some␈αexpressions,␈α
given␈αfirst␈α
in␈αinternal,␈α
then␈αin␈α
external␈αnotation.␈α
 You␈αshould
␈↓ ↓H␈↓evaluate␈αthese␈α
expressions,␈αby␈α
hand,␈αaccording␈α
to␈αthe␈α
rules␈αpresented␈α
in␈αChapter␈α
I.␈α When␈αyou␈α
are
␈↓ ↓H␈↓done␈α⊂go␈α⊃to␈α⊂LOTS␈α⊂and␈α⊃type␈α⊂the␈α⊃expressions␈α⊂(in␈α⊂internal␈α⊃form)␈α⊂to␈α⊂LISP␈α⊃and␈α⊂check␈α⊃the␈α⊂value
␈↓ ↓H␈↓returned␈αagainst␈αyour␈αanswer.␈α If␈αthere␈αis␈αsomething␈αyou␈αdon't␈αunderstand␈αtry␈α"stepping"␈αthrough
␈↓ ↓H␈↓the␈α
evaluation.␈α
 (See␈α
the␈α
MACLISP␈α
manual,␈α
or␈α
LISP␈α
at␈α
LOTS.)␈α
These␈α
exercises␈α
are␈α
to␈α∞get␈α
you
␈↓ ↓H␈↓going and not to be handed in.

␈↓ ↓H␈↓        Some␈α⊃of␈α⊂the␈α⊃expressions␈α⊂involve␈α⊃user␈α⊂defined␈α⊃programs.␈α⊂  The␈α⊃definitions␈α⊂are␈α⊃given␈α⊂in
␈↓ ↓H␈↓Chapter␈αI.␈α To␈αsave␈α
you␈αsome␈αtyping,␈αthe␈α
necessary␈αdefinitions␈αhave␈αbeen␈α
collected␈αin␈αa␈αfile␈α
which
␈↓ ↓H␈↓may be read in by typing:

␈↓ ↓H␈↓␈↓ ∧H␈↓↓␈↓¬(DSKIN (DSK |C.CS206|) HW0 F79).␈↓↓␈↓ 

␈↓ ↓H␈↓␈↓¬(QUOTE (A B C))␈↓
␈↓ ↓H␈↓␈↓¬(A B C)␈↓

␈↓ ↓H␈↓␈↓¬(QUOTE (A . (B . C)))␈↓    ;;;Note how LISP prints the value.
␈↓ ↓H␈↓␈↓¬(A B . C)␈↓

␈↓ ↓H␈↓␈↓¬(CADAR '((X (Y Z)) B C))␈↓
␈↓ ↓H␈↓␈↓↓␈↓αada|␈↓↓␈↓¬((X (Y Z)) B C)␈↓↓␈↓

␈↓ ↓H␈↓␈↓¬(FRINGE '(A . B))␈↓        ;;;␈↓↓fringe␈↓ is defined on page 17.
␈↓ ↓H␈↓␈↓↓fringe ␈↓¬(A . B)␈↓↓␈↓

␈↓ ↓H␈↓␈↓¬(FRINGE '(A B))␈↓
␈↓ ↓H␈↓␈↓↓fringe ␈↓¬(A B)␈↓↓␈↓

␈↓ ↓H␈↓␈↓¬(ASSOC 'X  '((Y . 1) (X . 5) (A . (1 2 3))))␈↓
␈↓ ↓H␈↓␈↓↓assoc[␈↓¬X␈↓↓, ␈↓¬((Y . 1) (X . 5) (A 1 2 3))␈↓↓]␈↓
␈↓ ↓H␈↓                                ;;;␈↓↓assoc␈↓ is defined on page 21

␈↓ ↓H␈↓␈↓¬(SUBST (CONS 1 NIL) '?X (CONS (CONS (CONS 'A 'B)'?X) NIL))␈↓
␈↓ ↓H␈↓␈↓↓subst[1 . ␈↓¬NIL␈↓↓, ␈↓¬?X␈↓↓, [[␈↓¬A␈↓↓ . ␈↓¬B␈↓↓] . ␈↓¬?X␈↓↓] . ␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓                                ;;;␈↓↓subst␈↓ is defined on page 16

␈↓ ↓H␈↓␈↓¬((LAMBDA (L) (LIST 'COND (LIST (CADR L) (CADDR L)) (LIST T (CADDDR L))))␈↓
␈↓ ↓H␈↓␈↓¬  '(IF (NULL NIL) NIL (CDR NIL)))␈↓
␈↓ ↓H␈↓␈↓↓[[λl: <␈↓¬COND␈↓↓, <␈↓αad|␈↓↓l, ␈↓αadd|␈↓↓l>, <␈↓¬T␈↓↓, ␈↓αaddd|␈↓↓l>>]␈↓
␈↓ ↓H␈↓␈↓↓ [␈↓¬(IF (NULL NIL) NIL (CDR NIL))␈↓↓]]␈↓

␈↓ ↓H␈↓␈↓¬(EVAL ((LAMBDA (L)␈↓
␈↓ ↓H␈↓␈↓¬         (LIST 'COND (LIST (CADR L) (CADDR L)) (LIST T (CADDDR L))))␈↓
␈↓ ↓H␈↓␈↓¬      '(IF (NULL NIL) NIL (CDR NIL)) ))␈↓

␈↓ ↓H␈↓␈↓↓eval [[λl: <␈↓¬COND␈↓↓, <␈↓αad|␈↓↓l, ␈↓αadd|␈↓↓l>, <␈↓¬T␈↓↓, ␈↓αaddd|␈↓↓l>>]␈↓
␈↓ ↓H␈↓␈↓↓      [␈↓¬(IF (NULL NIL) NIL (CDR NIL))␈↓↓]]␈↓
␈↓ ↓H␈↓␈↓¬(EXTENSIONS '(B A) ␈↓␈↓ ↓H␈↓␈↓ εH␈↓ 91
␈↓ ↓H␈↓␈↓¬            '((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E)))␈↓

␈↓ ↓H␈↓␈↓↓extensions[␈↓¬(B A)␈↓↓,␈↓
␈↓ ↓H␈↓␈↓↓␈↓¬         '((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E)))␈↓↓]␈↓

␈↓ ↓H␈↓where  ␈↓↓extensions␈↓ is a program to compute all extensions of length 1 of
␈↓ ↓H␈↓given path in a given graph.  (see page 2 for representation of graphs)

␈↓ ↓H␈↓␈↓¬(DEFUN EXTENSIONS  (PATH GRAPH)␈↓
␈↓ ↓H␈↓␈↓¬    (MAPCAR (FUNCTION (LAMBDA (X) (CONS X PATH)))␈↓
␈↓ ↓H␈↓␈↓¬          (CDR (ASSOC (CAR PATH) GRAPH))))␈↓
␈↓ ↓H␈↓                                ;;;␈↓↓mapcar␈↓ is defined on page 23

␈↓ ↓H␈↓␈↓¬(DIFF '(TIMES X  (PLUS Y 3) 1) 'X)␈↓   ;;;␈↓↓diff␈↓ is defined on page 24
␈↓ ↓H␈↓␈↓↓diff[␈↓¬(TIMES X (PLUS Y 3) 1)␈↓↓, ␈↓¬X␈↓↓]␈↓

␈↓ ↓H␈↓The␈αfollowing␈αexpressions␈αall␈αcontain␈αsome␈αsort␈αof␈αerror.␈α See␈αif␈αyou␈αcan␈αfind␈αthe␈αerror.␈α The␈α
type
␈↓ ↓H␈↓the␈αexpression␈αto␈α
LISP␈αso␈αsee␈α
what␈αsort␈αof␈α
error␈αmessage␈αyou␈α
get.␈α  (Remember␈αto␈αtype␈α
<control>G
␈↓ ↓H␈↓to get out to the "break-loop" after an error occurs.)

␈↓ ↓H␈↓¬(ATOM A)
␈↓ ↓H␈↓¬(CADR '((FOO.BAZ).GLUB))
␈↓ ↓H␈↓¬(CONS '(A B) (CONS 'C))
␈↓ ↓H␈↓¬(CONS ('(A B) 'C))
␈↓ ↓H␈↓¬(COND (ATOM '(A.B) T) (T (CDR '(A.B))))